import java.util.ArrayList;
import java.util.List;

/**
 * Shortest Ancestral Path (SAP)
 * http://coursera.cs.princeton.edu/algs4/testing/wordnet/
 */
public class SAP {

    private Digraph digraph;

    // constructor takes a digraph (not necessarily a DAG)
    public SAP(Digraph digraph) {

        this.digraph = new Digraph(digraph);
    }

    // length of shortest ancestral path between v and w; -1 if no such path
    public int length(int v, int w)  {

        List<Integer> vertexV = new ArrayList<Integer>();
        vertexV.add(v);
        List<Integer> vertexW = new ArrayList<Integer>();
        vertexW.add(w);
        return length(vertexV, vertexW);
    }

    // a common ancestor of v and w that participates in a shortest ancestral path
    public int ancestor(int v, int w) {

        List<Integer> vertexV = new ArrayList<Integer>();
        vertexV.add(v);
        List<Integer> vertexW = new ArrayList<Integer>();
        vertexW.add(w);
        return ancestor(vertexV, vertexW);
    }

    // length of shortest ancestral path between any vertex in v and any vertex in w
    public int length(Iterable<Integer> v, Iterable<Integer> w) {
        BreadthFirstDirectedPaths bfs1 = new BreadthFirstDirectedPaths(digraph, v);
        BreadthFirstDirectedPaths bfs2 = new BreadthFirstDirectedPaths(digraph, w);

        for (int x : v) {
            checkIndex(x);
        }
        for (int x : w) {
            checkIndex(x);
        }

        int minLength = Integer.MAX_VALUE;

        for (int i = 0; i < digraph.V(); i++) {
            if (bfs1.hasPathTo(i) && bfs2.hasPathTo(i)) {
                int totLength = bfs1.distTo(i) + bfs2.distTo(i);
                minLength = Math.min(minLength, totLength);
            }
        }

        //if MAX_VALUE return -1, that means path does not exist
        return (minLength == Integer.MAX_VALUE ? -1 : minLength);
    }

    // a common ancestor that participates in shortest ancestral path; -1 if no such path
    public int ancestor(Iterable<Integer> v, Iterable<Integer> w) {
        BreadthFirstDirectedPaths bfs1 = new BreadthFirstDirectedPaths(digraph, v);
        BreadthFirstDirectedPaths bfs2 = new BreadthFirstDirectedPaths(digraph, w);
        int minLength = Integer.MAX_VALUE;
        int ancestor = Integer.MAX_VALUE;

        for (int i = 0; i < digraph.V(); i++) {
            if (bfs1.hasPathTo(i) && bfs2.hasPathTo(i)) {
                int totLength = bfs1.distTo(i) + bfs2.distTo(i);
                if (totLength < minLength) {
                    ancestor = i;
                    minLength = totLength;
                }
            }
        }

        //if MAX_VALUE return -1, that means path does not exist
        return (ancestor == Integer.MAX_VALUE ? -1 : ancestor);
    }

    private void checkIndex(int v) {
        if (v < 0 || v >= digraph.V()) {
            throw new IndexOutOfBoundsException();
        }
    }

    public static void main(String[] args) {

        In in = new In(args[0]);
        Digraph G = new Digraph(in);
        SAP sap = new SAP(G);
//            while (!StdIn.isEmpty()) {
//                int v = StdIn.readInt();
//                int w = StdIn.readInt();
//                int length   = sap.length(v, w);
//                int ancestor = sap.ancestor(v, w);
//                StdOut.printf("length = %d, ancestor = %d\n", length, ancestor);
//            }

        int minLength = sap.length(3, 11);
        int ancestor = sap.ancestor(3, 11);
        StdOut.printf("from %d to %d\n", 3, 11);
        StdOut.printf("%d : min length\n", minLength);
        StdOut.printf("%d : ancestor\n", ancestor);

        minLength = sap.length(1, 6);
        ancestor = sap.ancestor(1, 6);
        StdOut.printf("from %d to %d\n", 1, 6);
        StdOut.printf("%d : min length\n", minLength);
        StdOut.printf("%d : ancestor\n", ancestor);


    }

}